package sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/6 21:12
 */
public class Sort总复习 {




    /*
      选择 排序
     */
    @Test
    public void test(){
        int arr[] = {5,3,3,2,1};
        for(int i = 0;i < arr.length - 1;i++){
            int minIndex = i;
            for(int j = i + 1;j < arr.length;j++){
                /*
                 注意 这里 >  而不是 ( >= ) 是为了 保证 稳定性!
                 */
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
        System.out.println(Arrays.toString(arr));
    }


    /*
    冒泡 排序
   */
    @Test
    public void test1() {
        int arr[] = {5, 3, 4, 3, 2, 1};
        for(int i = arr.length - 1;i >= 0;i--){
            for(int j = 0;j < i;j++){
                if(arr[j] > arr[j + 1]){
                    swap(arr,j,j + 1);
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }



    /*
     插入 排序
     这个 排序 最初,既然 还没有 回想 起来, 这就很离谱
   */
    @Test
    public void test2() {
        int arr[] = {5, 3, 3, 2, 1};
        for(int i = 1;i < arr.length;i++){
            int temp = arr[i];
            int j;
            for( j = i - 1; j >= 0;j-- ){
                if(arr[j] > temp){
                    arr[j + 1] = arr[j];
                }
            }
            arr[j + 1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }


/*
  归并排序
 */
    @Test
    public void test3(){
        int arr[] = {5, 3, 4,3, 2, 1};
        mergeSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    private void mergeSort(int arr[],int l,int r){
        if(l == r){
//            return arr[l];
            return ;
        }
        int mid = l + r >> 1;
        mergeSort(arr,0,mid);
        mergeSort(arr,mid + 1,r);
        merge(arr,l,mid,r);

    }

    /*
     直接 在 原来的 数组上进行操作 , 通过 mid , 将数组的 l ~ r 范围, 逻辑分成两个数组
     */
    private void merge(int[] arr, int l, int mid, int r) {
        int helper[] = new int[r - l + 1];
        int p1 = l,p2 = mid + 1,index = 0;
        while (p1 <= mid && p2 <= r ) {
            if(arr[p1]  <= arr[p2]){
                helper[index++] = arr[p1++];
            }
            else{
                helper[index++] = arr[p2++];
            }
        }
        while(p1 <= mid){
            helper[index++] = arr[p1++];
        }
        while(p2 <= r){
            helper[index++] = arr[p2++];
        }
        /*
            在将 有序的 helper 数组 copy 回原来的  arr 数组
            注意 这里 , 最初的 想法 是 , 直接 把  arr = helper ( 通过 引用 指向, 这种思想 不太对 , 传入 的 参数 arr 是 最初 数组 arr 引用 变量的 一个 副本(copy))


         */
        for(int num : helper){
            arr[l++] = num;
        }
    }





    /*
      堆排序 ( 重点 ) , 尤其 是 这种 数据结构
     */








    /*
    swap 函数
     */
    private void swap(int nums[],int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
